// https://www.lintcode.com/problem/moving-average-from-data-stream/description
// 给出一串整数流和窗口大小，计算滑动窗口中所有整数的平均值。

// 样例
// MovingAverage m = new MovingAverage(3);
// m.next(1) = 1 // 返回 1.00000
// m.next(10) = (1 + 10) / 2 // 返回 5.50000
// m.next(3) = (1 + 10 + 3) / 3 // 返回 4.66667
// m.next(5) = (10 + 3 + 5) / 3 // 返回 6.00000


// 法一：O(size)
// class MovingAverage {
// private:
//     vector<int> nums;
//     int len;
// public:
//     /*
//     * @param size: An integer
//     */
//     MovingAverage(int size) {
//         this->len = size;
//     }

//     /*
//      * @param val: An integer
//      * @return:  
//      */
//     double next(int val) {
//         nums.push_back(val);
//         if (nums.size() > len)
//         {
//             nums.erase(nums.begin());
//         }
//         double sum = 0;
//         for (int i = 0; i < nums.size(); i++)
//         {
//             sum += nums[i];
//         }
//         return sum / nums.size();
//     }
// };

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param = obj.next(val);
 */


 
 // 法二：前缀和数组
    // • 什么是前缀和数组？
    // – 下表中a是原始数组
    // – 定义s是a的前缀和数组，s[i] = a[1] + a[2] + a[3] …. + a[i]
    // • 方便快速求a数组中某一段的和
    // – a[k] + a[k + 1] +… + a[j] = s[j] - s[k -1] 时间复杂度o(1)
    // • 怎样快求s数组？
    // – s[i] = s[i - 1] + a[i] 时间复杂度o(n)
    
    // • 如何节省储存空间呢？（2种方法）
    // 1. 链表保存sum
    // 2. 数组滚动：• 怎样得到实际位置？
    // – 逻辑位置取mod，这一题mod (size+1)。怕出错可以开大一点
    // 空间复杂度：O(size)

    // ◆ 小技巧总结：
    // • 如何快速求和？ 前缀和数组(dummy 0)
    // • 如何节省储存空间呢？ 链表/滚动
    // • 写滚动的技巧 先写程序最后加滚动
    // • 滚动的应用：
    // – DP 背包问题 backpack 系列
    // – BFS 中的循环队列

// v0:静态数组
// class MovingAverage {
// private:
//     vector<double> sum;
//     int id, size;
// public:
//     /*
//     * @param size: An integer
//     */
//     MovingAverage(int size) 
//     {
//         sum = vector<double>(1000000, 0);
//         id = 0;
//         this->size = size;
//     }

//     /*
//      * @param val: An integer
//      * @return:  
//      */
   
//     double next(int val) 
//     {
//         id++;
//         sum[id] = sum[id - 1] + val;
//         if (id > size)
//         {
//             return (sum[id] - sum[id - size]) / size;
//         }
//         else
//         {
//             return sum[id] / id;
//         }
//     }
// };

// v1:滚动数组
// class MovingAverage {
// private:
//     vector<double> sum;
//     int id, size;
// public:
//     /*
//     * @param size: An integer
//     */
//     MovingAverage(int size) 
//     {
//         sum = vector<double>(size + 1, 0);
//         id = 0;
//         this->size = size;
//     }

//     /*
//      * @param val: An integer
//      * @return:  
//      */
//     int mod (int x) 
//     {
//         return x % (size + 1);
//     }
     
//     double next(int val) 
//     {
//         id++;
//         sum[mod(id)] = sum[mod(id-1)] + val;
//         if (id > size)
//         {
//             return (sum[mod(id)] - sum[mod(id - size)]) / size;
//         }
//         else
//         {
//             return sum[mod(id)] / id;
//         }
//     }
// };

// v2:链表
// erase之后id也变，不需要记录id
class MovingAverage {
private:
    vector<double> sum;
    int id, size;
public:
    /*
    * @param size: An integer
    */
    MovingAverage(int size) 
    {
        this->size = size;
        sum.push_back(0);
    }

    /*
     * @param val: An integer
     * @return:  
     */
     
    double next(int val) 
    {
        sum.push_back(sum.back() + val);
        if (sum.size() > size + 1)
        {
            sum.erase(sum.begin()); 
            return (sum.back() - sum.front()) / size;
        }
        else
        {
            return sum.back() / (sum.size() - 1);
        }
    }
};